package binarysearch;
import java.util.*;

// 计数二分
// https://binarysearch.com/problems/Kth-Pair-Distance
class 找到数组中任意两个数差的绝对值第k小的差值 {
            public int solve(int[] nums, int k) {
                k += 1; 
                Arrays.sort(nums);
                int l = 0, r = nums[nums.length - 1] - nums[0];
                while( l < r) {
                    int mid = (l + r) >> 1;
                    //   看差值mid 之前有多少更小的差值数字  加起看是否大于等于k 如果大于等于k了 说明mid取大了
                    boolean ok = moreThanOrEqualsK(mid, k, nums);
                    // find a value 
                    if(ok){
                        r = mid;  
                    } else {
                        l = mid + 1;
                    }
                }
                return l;
            }

            private boolean moreThanOrEqualsK(int mid, int k, int[] numsSorted) {
                int pairsDiffGreaterThanKCnt = 0;
                for(int l = 0, r = 0; l < numsSorted.length; l++) {
                    // 求差值要小于等于 mid的有多少对数字  如 1 2 3 4 第一小的是1 
                    // 差值  4， 3， 2，2， 1 中小于等于3的有4个 重复的也算
                    while((r < numsSorted.length) && (numsSorted[r] - numsSorted[l]) <= mid) {r ++;}; 
                    if( (pairsDiffGreaterThanKCnt += (r-l-1) ) >= k) return true;

                }
                return false;
            }
        }